1. Technical Field
The invention disclosed broadly relates to data processing and data communications and more particularly relates to techniques for maintaining data throughput in a packet switching local area network under changing traffic load.
2. Background Art
Local area networks are communications systems for transferring data among a plurality of workstation terminals, peripheral devices, cluster controllers, or host systems within the bounds of a single office building or building complex. A node refers to any machine or combination of machines which attaches to and uses the local area network. Local area network architectures allow for the attachment of many nodes to a common physical link. The shared access link permits any node to communicate directly with any other node attached to the link through the propagation of electrical signals and the logical connections established by link protocols. Data is transferred as packets consisting of a variable-length information field preceded by appropriate addressing fields. Two general types of physical link topologies are used for shared access links, the ring and the bus. A ring consists of a series of nodes which are connected by unidirectional transmission links to form a single closed path. Information signals on the ring pass from node to node and are regenerated as they pass through each node. The bus type of link provides a bidirectional transmission facility to which all nodes are attached. Information signals propagate away from the originating node in both directions to the terminated ends of the bus.
The topology of a ring or a bus shared access link permits simultaneous access to the medium by all attached nodes. Thus it is possible for two or more nodes to attempt transmission at the same time resulting in interference between the signals. Both physical and logical control mechanisms are employed to resolve the contention for access. Time division multiplexing separates the energy of the two signals into different periods of time. The time division multiplexing (TDM) of digital information can be synchronous TDM or asynchronous TDM. Synchronous TDM allows each node to use a portion of the bandwidth for the medium at periodic intervals. Asynchronous TDM allows each node to transmit for a variable length of time. The data is blocked into packets that contain appropriate addressing information for routing the data. A logical control mechanism must be employed in conjunction with asynchronous TDM to regulate each node's access to the link for transmission.
For a bus topology, one access control mechanism is called the carrier sense multiple access with collision (CSMA/CD). This access method is described in the IEEE Standard 802.3, CSMA/CD Access Method and Physical Layer Specifications. Prior to initiating transmission, a node senses whether a carrier signal is present since this indicates that another node is transmitting. The origination of a new transmission will be delayed by the node until the carrier signal is removed. Once the node's transmission is started, it continues to monitor the transmission for a collision, that is the destruction of the transmitted electrical signals indicating the presence of another transmitting node. In the event of a collision, transmission is halted and the node either waits a random period of time before attempting to retransmit, or waits for a predetermined time interval.
An example access method for transmission of packets on a ring topology is the token ring multiple access (TRMA) method. In this distributed control access method, a unique sequence, called a token, is passed from one node to another. The receipt by a node of the token gives it permission to initiate a transmission. Upon the completion of the transmission, the token is passed to another node. For a ring, this token is passed implicitly, that is without addressing information, to the next node on the ring. In a bus topology, an explicit token which contains specific node address information is employed. The explicit token approach creates an ordering of the nodes which can be described as a logical ring. Token ring characteristics are specified in IEEE Project 802 Local Area Network Standards, Draft IEEE Standard 802.5, Token Ring Access Method and Physical Layer Specifications, working draft (February 1984). Additional references providing a background on token ring local area networks include an article by N. C. Strole entitled "A Local Communications Network Based on Interconnected Token Access Rings: A Tutorial," IBM Journal of Research and Development, Vol. 27, No. 5, September 1983, pp. 481-496, an article by R. C. Dixon, et al. entitled "A Token Ring Network for Local Data Communications," IBM Systems Journal, Vol. 22, Nos. 1-2, 1983, pp. 47-62.
A problem shared by all multiple access packet switching local area networks is that the time which must be devoted to resolving the contentions for access by the nodes becomes an increasing function of the network loading. The network loading can be characterized by the duty factor .rho., otherwise known as the bandwidth utilization efficiency which is the ratio of the present information flow rate R (in bits per second) divided by the maximum capacity information flow rate Ro (in bits per second). As the information flow rate or the duty factor increases, the packet delay time T, which is the average waiting time for a node to obtain access to the communications medium and to successfully transmit the packet, increases. Although the relationship between the reduction in performance and the increase in network loading varies among the various types of access methods, all access methods for packet transmission on a multiple access communications link suffer this degraded operating characteristic. If the overloading condition continues to increase, the network becomes unstable with many nodes being unable to obtain any access to the communications medium for long periods of time.
Attempts have been made in the prior art to provide an adaptive control method to reduced the instability resulting from network loading. The following references disclose adaptive control procedures for CSMA/CD access method, where the random waiting time for retransmission is changed as a function of network load.
1. F. A. Tobagi and L. Kleinrock, "Packet Switching in Radio Channels: Part IV, Stability Considerations and Dynamic Control in Carrier Sense Multiple Access," IEEE Transactions on Communications, Vol. COM-25, pp. 1400-1416, December 1975.
2. S. S. Lam, "A Carrier Sense Multiple Access Protocol for Local Networks," Computer Networks, Vol. 4, pp. 21-32, January-February, 1980.
3. F. Tobagi and V. Hunt, "Performance Analysis of Carrier Sense Multiple Access with Collision Detection," Computer Networks, Vol. 4, pp. 245-259, October-November 1980.
4. I. Rubin, "Synchronous and Carrier Sense Asynchronous Dynamic Group Random Access Schemes for Multiple Access Communications," IEEE Transactions on Communications, Vol. COM-31, pp. 1063-1077, September 1983.
5. J. S. Meditch and C. T. A. Lea, "Stability and Optimization of the CSMA and CSMA/CD Channels," IEEE Transactions on Communications, Vol. COM-31, pp. 763-774, June 1983.
Other discussions of performance characteristics for local area networks can be found in:
6. W. Bux, "Performance Issues in Local Area Networks," IBM Systems Journal, Vol. 23, No. 4, 1984.
7. Michael J. Firguson, and Yehuda J. Aminetzah, "Exact Results for Nonsymmetric Token Ring Systems," IEEE Transactions on Communications, Vol. COM-33, No. 3, March 1985.
8. W. Bux, "Local--Area Subnetworks; A Performance Comparison," IEEE Transactions on Communications, Vol. COM-9, No. 10, October 1981.
The problem with this approach is that there is no attempt to maintain a network traffic at a fixed value since the effect of this prior art technique is to either drop or reduce the traffic at some nodes while accommodating the traffic at other nodes in order to maintain network stability. This substantially reduces the overall data throughput for the network since data flow control signals must be passed back to the sources of the information to be transmitted signaling them to reduce their rate of delivery of information to be transmitted on the local area network.